import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网链表OJ练习
 */

class Solution {
    public static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode head;

    //反转链表的全部
    public ListNode ReverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    //反转链表的m~n的节点,链表从1开始
    public ListNode reverseBetween1 (ListNode head, int m, int n) {
        if(head == null || head.next == null || m == n) {
            return head;
        }
        int count = 1;
        ListNode cur = head;
        while(cur != null && count < m - 1) {
            cur = cur.next;
            count++;
        }
        ListNode curFront = null;
        if(m != 1) {
            curFront = cur;
            cur = cur.next;
            count++;
        }
        ListNode newHead = cur;
        if(cur != null) {
            cur = cur.next;
        }else{
            return head;
        }
        while(cur != null && count < n) {
            ListNode curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
            count++;
        }
        if(curFront == null) {
            head.next = cur;
            head = newHead;
        }else{
            curFront.next.next = cur;
            curFront.next = newHead;
        }
        return head;
    }

    //优化：创建虚拟头节点
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //仍然开局先判断，无论是下面哪种情况，我们都直接返回head
        if(head == null || head.next == null || m == n) {
            return head;
        }
        //创建虚拟头节点，并且让虚拟头节点的下一个节点指向head
        ListNode falseHead = new ListNode(-1,null);
        falseHead.next = head;
        //从虚拟头节点开始遍历
        int count = 0;
        ListNode cur = falseHead;
        //如果m = 1，那么不会进入循环，此时cur仍指向了m的前一个节点
        while(cur != null && count < m - 1) {
            cur = cur.next;
            count++;
        }
        //保存m的前一个节点
        ListNode curLeft = cur;
        //实例化一个头节点，作为链表的反转部分的头节点
        ListNode newHead = cur.next;
        //cur需要反转，就要指向反转部分的第二个节点
        cur = cur.next.next;
        //count的值与cur保持一致
        count += 2;
        //将链表的部分进行反转
        while(cur != null && count <= n) {
            ListNode curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
            count++;
        }
        //反转结束，cur指向了反转部分最后一个节点的下一个节点，保存起来
        ListNode curRight = cur;
        //将前，中，后三部分连接起来
        //因为此时curLeft.next指向了反转之后的最后一个节点
        curLeft.next.next = curRight;
        curLeft.next = newHead;
        //返回虚拟头节点的下一个节点
        return falseHead.next;
    }

    //链表中的节点每k个一组翻转
    public ListNode reverseKGroup(ListNode head, int k) {
        // write code here
        //开局照例判断，下面三种情况都可以直接返回head
        if(head == null || head.next == null || k <= 1) {
            return head;
        }
        ListNode cur = head;
        //统计链表节点的个数
        int length = 0;
        while(cur != null) {
            cur = cur.next;
            length++;
        }
        //由上一道题可知，创建一个虚拟头节点会省事很多
        ListNode falseHead = new ListNode(-1,null);
        falseHead.next = head;
        //count定义在外面，用来记录翻转到第几个节点了
        int count = 1;
        //首先需要定义两个节点作为翻转组的前后节点，再定义一个反转组的头节点
        //直接定义在for循环外面，这样就不需要每次都要遍历进行寻找
        ListNode curLeft = falseHead;
        ListNode curRight;
        ListNode newHead = head;
        //在for循环前，让cur指向head.next
        cur = head.next;
        //用for循环来控制要翻转几组
        for(int i = 0; i < length / k;i++) {
            //n记录翻转组的最后一个节点的位置
            //第一个节点不用记，因为翻转是从头开始的
            int n = k * (i + 1);
            //此时我们不需要再寻找，因为是从头节点开始
            //进行翻转
            while(cur != null && count < n) {
                ListNode curNext = cur.next;
                cur.next = newHead;
                newHead = cur;
                cur = curNext;
                count++;
            }
            //翻转完成之后cur指向该组节点的下一个节点，即curRight的位置
            curRight = cur;
            //由于下一次翻转还需要前一个位置的节点，因此需要此时就得到前一个
            //位置的节点
            ListNode temp = curLeft.next;
            //将原链表与翻转链表相连接
            curLeft.next.next = curRight;
            curLeft.next = newHead;
            //将curLeft引用的对象改为下一组的前一个节点
            curLeft = temp;
            //newhead指向下一组的第一个节点，cur指向下一组的第二个节点
            newHead = cur;
            if(cur != null) {
                //新的一组开始，count的值也要变成下一组的第一个节点
                count++;
                cur = cur.next;
            }
        }
        return falseHead.next;
    }

    //合并两个排序的链表
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(0,null);
        ListNode tail = head;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
            }else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        if(list1 != null) {
            while(list1 != null) {
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            }
        }
        if(list2 != null) {
            while(list2 != null) {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
        }
        return head.next;
    }

    //合并K个已排序的链表
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.size() <= 1) {
            return lists.get(0);
        }
        for(int i = 0; i + 1 < lists.size(); i++) {
            ListNode cur1 = lists.get(i);
            ListNode cur2 = lists.get(i + 1);
            lists.remove(i);
            lists.remove(i);
            ListNode head = new ListNode(0,null);
            ListNode tail = head;
            while(cur1 != null && cur2 != null) {
                if(cur1.val < cur2.val) {
                    tail.next = cur1;
                    cur1 = cur1.next;
                }else {
                    tail.next = cur2;
                    cur2 = cur2.next;
                }
                tail = tail.next;
            }
            if(cur1 != null) {
                tail.next = cur1;
                cur1 = cur1.next;
                tail = tail.next;
            }
            if(cur2 != null) {
                tail.next = cur2;
                cur2 = cur2.next;
                tail = tail.next;
            }
            lists.add(i,head.next);
        }
        return mergeKLists(lists);
    }

    //判断链表中是否有环
    public boolean hasCycle(ListNode head) {
        //快慢指针
        if(head == null || head.next == null) {
            return false;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }

    //得到链表中环的入口节点（如果没有环，return null）
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                break;
            }
        }
        if(fast.next == null || fast.next.next == null) {
            return null;
        }
        slow = pHead;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }

    //链表中倒数最后K个节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if(pHead == null || k <= 0) {
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(k > 0) {
            if(fast == null) {
                return null;
            }
            fast = fast.next;
            k--;
        }
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    //删除链表的倒数第 n 个节点
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if(head == null || n <= 0) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode slowFront = null;
        while(n > 0) {
            if(fast == null) {
                return head;
            }
            fast = fast.next;
            n--;
        }
        //考虑删除头节点
        if(fast == null) {
            return head = head.next;
        }
        while(fast != null) {
            fast = fast.next;
            slowFront = slow;
            slow = slow.next;
        }
        slowFront.next = slow.next;
        return head;
    }

    //两个链表的第一个公共节点
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int count1 = 0;
        int count2 = 0;
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while(cur1 != null) {
            count1++;
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            count2++;
            cur2 = cur2.next;
        }
        cur1 = pHead1;
        cur2 = pHead2;
        while(count1 > count2) {
            cur1 = cur1.next;
            count1--;
        }
        while(count1 < count2) {
            cur2 = cur2.next;
            count2--;
        }
        while(cur1 != null && cur2 != null) {
            if(cur1 == cur2) {
                return cur1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }

    //链表相加（二）类似高精度算法，采用辅助栈
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if(head1 == null && head2 == null) {
            return new ListNode(0,null);
        }
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        ListNode cur = head1;
        while(cur != null) {
            stack1.push(cur.val);
            cur = cur.next;
        }
        cur = head2;
        while(cur != null) {
            stack2.push(cur.val);
            cur = cur.next;
        }
        if(stack1.empty()) {
            return head2;
        }
        if(stack2.empty()) {
            return head1;
        }
        ListNode head = null;
        //进位需要保存，不能放在循环里一直赋值
        int carry = 0;
        while(!stack1.empty() && !stack2.empty()) {
            int addend1 = stack1.pop();
            int addend2 = stack2.pop();
            int sum = (addend1 + addend2 + carry) % 10;
            carry = (addend1 + addend2 + carry) / 10;
            //头插法创建结果链表
            head = addFist(head,sum);
        }
        while(!stack1.empty()) {
            int addend1 = stack1.pop();
            int sum = (addend1 + carry) % 10;
            carry = (addend1 + carry) / 10;
            head = addFist(head,sum);
        }
        while(!stack2.empty()) {
            int addend2 = stack2.pop();
            int sum = (addend2 + carry) % 10;
            carry = (addend2 + carry) / 10;
            head = addFist(head,sum);
        }
        if(carry != 0) {
            head = addFist(head,carry);
        }
        return head;
    }
    private static ListNode addFist(ListNode head,int val) {
        if(head == null) {
            return new ListNode(val,null);
        }
        ListNode cur = new ListNode(val,null);
        cur.next = head;
        head = cur;
        return head;
    }

    //单链表的排序，归并排序的应用
    public ListNode sortInList (ListNode head) {
        // write code here
        //归并排序时间复杂度较低且不受元素值的影响，是理想的排序方法
        //有序的元素之间进行归并，就是两个有序链表进行归并
        if(head == null || head.next == null) {
            return head;
        }
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head){
        if(head.next == null) {
            return head;
        }
        //1.遍历找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        ListNode slowFront = null;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slowFront = slow;
            slow = slow.next;
        }
        slowFront.next = null;
        head = mergeSort(head);
        slow = mergeSort(slow);
        ListNode curHead = head;
        ListNode curSlow = slow;
        ListNode newHead = null;
        ListNode newTail = null;
        while(curHead != null && curSlow != null) {
            if(curHead.val <= curSlow.val){
                newTail = tailAdd(newTail,curHead.val);
                curHead = curHead.next;
            }else {
                newTail = tailAdd(newTail,curSlow.val);
                curSlow = curSlow.next;
            }
            if(newHead == null){
                newHead = newTail;
            }
        }
        while(curHead != null) {
            newTail = tailAdd(newTail,curHead.val);
            curHead = curHead.next;
        }
        while(curSlow != null) {
            newTail = tailAdd(newTail,curSlow.val);
            curSlow = curSlow.next;
        }
        return newHead;
    }

    private ListNode tailAdd(ListNode tail,int val) {
        if(tail == null) {
            tail = new ListNode(val,null);
        }else {
            tail.next = new ListNode(val,null);
            tail = tail.next;
        }
        return tail;
    }

    //判断一个链表是否为回文结构
    public boolean isPail (ListNode head) {
        // write code here
        if(head == null) {
            return false;
        }
        if(head.next == null) {
            return true;
        }
        //1.快慢指针，找到中间节点
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //2.翻转
        ListNode headRight = slow.next;
        slow.next = null;
        headRight = reversal(headRight);
        //3.对比
        while(head != null && headRight != null) {
            if(head.val != headRight.val) {
                return false;
            }
            head = head.next;
            headRight = headRight.next;
        }
        return true;
    }

    private ListNode reversal(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode newHead = null;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = newHead;
            newHead = cur;
            cur = curNext;
        }
        return newHead;
    }

    //链表的奇偶重排
    public ListNode oddEvenList (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        //分别设立两个虚拟头节点，把原链表从头到尾拆下来再并一起
        ListNode newHeadLeft = new ListNode(0,null);
        newHeadLeft.next = head;
        ListNode cur1 = head;
        ListNode newHeadRight = new ListNode(0,null);
        newHeadRight.next = head.next;
        ListNode cur2 = head.next;
        int count = 0;
        head = head.next.next;
        while(head != null) {
            count++;
            if(count % 2 == 1) {
                cur1.next = head;
                cur1 = cur1.next;
            }else {
                cur2.next = head;
                cur2 = cur2.next;
            }
            head = head.next;
        }
        cur2.next = null;
        cur1.next = newHeadRight.next;
        return newHeadLeft.next;
    }

    //删除有序链表中的重复的元素-1
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while(cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
                continue;
            }
            cur = cur.next;
        }
        return head;
    }

    //删除有序链表中重复的元素-2
    public ListNode deleteDuplicates2 (ListNode head) {
        // write code here
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = new ListNode(0,null);
        //tail作为尾节点
        ListNode tail = newHead;
        tail.next = head;
        ListNode fast = head;
        //每一次判断的时候，fast的节点与tail.next保持一致
        //即每次判断的都是tail.next
        //每一次tail.next要么是重复节点之后的第一个节点
        //要么是不重复节点的下一个节点
        //因此如果tail.next是最后一个节点
        //那么fast.next == null，一定不会重复
        while(fast != null && fast.next != null) {
            if(fast.val == fast.next.val) {
                int tmp = fast.val;
                //当fast.next.val == tmp时，让fast = fast.next;
                while(fast.next != null && tmp == fast.next.val) {
                    fast = fast.next;
                }
                //循环结束时，
                //1.fast.next == null，此时fast在链表的尾节点
                //表示tail后面都是重复的
                //那么就让tail.next指向尾节点的next，即null
                //2.tmp != fast.next.val，表示fast.next是一个新的节点
                //tail.next 换成 fast.next，之后测试这个新的节点
                tail.next = fast.next;
                //fast作为tail.next的测试节点，应该与tail.next保持一致
                fast = fast.next;
            } else {
                tail = tail.next;
                fast = fast.next;
            }
        }
        return newHead.next;
    }
}

public class Test {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        //使用正向迭代器，正向遍历
        ListIterator<Integer> listIterator = list.listIterator();
        while(listIterator.hasNext()) {
            System.out.print(listIterator.next() + " ");
        }
        System.out.println();
        System.out.println("====================");
        //使用反向迭代器，反向遍历
        ListIterator<Integer> listIterator1 = list.listIterator(list.size());
        while(listIterator1.hasPrevious()) {
            System.out.print(listIterator1.previous() + " ");
        }
    }


    public static void main1(String[] args) {
        Solution solution = new Solution();
        Solution.ListNode node6 = new Solution.ListNode(5,null);
        Solution.ListNode node5 = new Solution.ListNode(4,node6);
        Solution.ListNode node2 = new Solution.ListNode(2,node5);
        Solution.ListNode node3 = new Solution.ListNode(3,node2);
        Solution.ListNode root = new Solution.ListNode(1,node3);

        /*ArrayList<Solution.ListNode> lists = new ArrayList<>();
        lists.add(node1);
        lists.add(node4);
        lists.add(node7);
        *//*solution.ReverseList(node1);*//*
        *//*solution.reverseBetween(node1,2,4);*//*
        *//*solution.reverseKGroup(node1,2);*//*
        solution.mergeKLists(lists);*/
        Solution.ListNode newHead = solution.sortInList(root);
        System.out.println("kflgjdg");
    }
}
